今天要面對的問題是如何判斷一個字串是 Palindrome．
所謂 Palindrome 字串就是正著念倒著念都一樣，例如黑吃黑、多倫多、石榴石、文言文、鹽酸鹽、禹英禑．

問題

https://leetcode.com/problems/valid-palindrome/

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

提示

字串大小寫轉換:

Python

lowerStr = oldStr.lower()
upperStr = oldStr.upper()

Go

import "strings"
lowerStr := strings.ToLower(oldStr)
upperStr := strings.ToUpper(oldStr)

移除所有非英文字母及數字的字元:

Python

Python 可以使用 isalnum() 函式來檢查每一個字元是否是英文或數字．
然後再將英文或數字的字元組成的陣列用 join() 函式來組成新的字串.

oldStr = "alphanumeric@123__"
newStr = ''.join(ch for ch in oldStr if ch.isalnum())

檢查每一個字元時，除了用 item for item in iterable if function(item)來處理，也可以用 filter(function, iterable) 函式取代．

例如：

oldStr = "alphanumeric@123__"
newStr = ''.join(filter(str.isalnum, oldStr))

Go

Go 沒有 isalnum , 但我們可以利用正規表示法來移除非英文字母的字元.

package main

import (
	"fmt"
	"regexp"
)

func main() {
	oldStr := "alphanumericABCXYZ_-@123"
    nonAlphanumericRegex := regexp.MustCompile(`[^a-zA-Z0-9 ]+`)
	newStr := nonAlphanumericRegex.ReplaceAllString(oldStr, "")
	fmt.Println(newStr)
}

我的答案

前後一一比較字元看是否相同

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newS = ''.join(filter(str.isalnum, s.lower()))

        i, j = 0, len(newS)-1
        while i < j:
            if newS[i] == newS[j]:
                i += 1
                j -= 1
            else:
                return False

        return True

Go

import (
    "strings"
    "regexp"
)

func isPalindrome(s string) bool {
    nonAlphanumericRegex := regexp.MustCompile(`[^a-z0-9]+`)
    newS := nonAlphanumericRegex.ReplaceAllString(strings.ToLower(s), "")

    i := 0
    j := len(newS)-1
    for i < j {
        if newS[i] == newS[j] {
            i++
            j--
        } else {
            return false
        }
    }
    return true
}